
package cloning.cci4.ch1;

/*
 * Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer.
 *  NOTE: One or two additional variables are fine. An extra copy of the array is not.
 * FOLLOW UP
 * Write the test cases for this method.
 * 
 */

public class Task_1_3
{

	public static void main(String[] args)
	{
		String first = "abcde";
		String second = "abcdee";
		String third = "aabbccddee";

		// removeDuplicateChars(first);
		// removeDuplicateChars(second);
		// removeDuplicateChars(third.toCharArray());

		char[] thirdArray = third.toCharArray();
		removeDuplicateChars(thirdArray);

		// printChars(thirdArray);
	}

	private static void removeDuplicateChars(char[] charArray)
	{
		printChars(charArray);
		char[] result = new char[charArray.length];
		int currentFilledResultIndex = 0;

		for (int index = 0; index < charArray.length; index++)
		{
			char currentInputChar = charArray[index];

			boolean dublicate = false;

			for (int resultIndex = 0; resultIndex < result.length; resultIndex++)
			{
				if (currentInputChar == result[resultIndex])
				{
					dublicate = true;
					break;
				}
			}

			if (!dublicate)
			{
				result[currentFilledResultIndex] = currentInputChar;
				currentFilledResultIndex++;
			}

		}

		printChars(result);
	}

	private static void printChars(char[] string)
	{
		for (int i = 0; i < string.length; i++)
		{
			System.out.print(string[i]);
		}
		System.out.print("\n");
	}

	public static void removeDuplicates(char[] str)
	{
		if (str == null)
			return; // if the array does not exist..nothing to do return.
		int len = str.length; // get the array length.
		if (len < 2)
			return; // if its less than 2..can't have duplicates..return.
		int tail = 1; // number of unique char in the array.
		// start at 2nd char and go till the end of the array.
		for (int i = 1; i < len; ++i)
		{
			int j;
			// for every char in outer loop check if that char is already seen.
			// char in [0,tail) are all unique.
			for (j = 0; j < tail; ++j)
			{
				if (str[i] == str[j])
					break; // break if we find duplicate.
			}
			// if j reachs tail..we did not break, which implies this char at
			// pos i
			// is not a duplicate. So we need to add it our "unique char list"
			// we add it to the end, that is at pos tail.
			if (j == tail)
			{
				str[tail] = str[i]; // add
				++tail; // increment tail...[0,tail) is still "unique char list"
			}
		}
		str[tail] = 0; // add a 0 at the end to mark the end of the unique char.

		printChars(str);

	}

	public static void removeDuplicates1(char[] str)
	{

		if (str == null)
			return;
		int len = str.length;
		if (len < 2)
			return;
		boolean[] hit = new boolean[256];
		for (int i = 0; i < 256; ++i)
		{
			hit[i] = false;
		}
		hit[str[0]] = true;
		int tail = 1;
		for (int i = 1; i < len; ++i)
		{
			if (!hit[str[i]])
			{
				str[tail] = str[i];
				++tail;
				hit[str[i]] = true;
			}
		}
		str[tail] = 0;

		printChars(str);
	}
}
